//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
// Related Topics 数组 回溯 
// 👍 783 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class Combinations {
    public static void main(String[] args) {
        new Combinations().new Solution().combine(4, 2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * dfs的时候给一个起点值，因为不能重复出现，所以下次dfs的时候需要起点+1
     * 递归搜索时存在一个上边界值，同tempSize k n 三个数共同决定
     * 比如 n = 6 k = 4 size = 1的时候，需要再找3个数，此时搜索上限是4(n-(k-size)+1)
     * 因为5以及之后不存在三个数了，所以也就没必要检索了
     *
     */
    class Solution {
        List<Integer> temp;
        List<List<Integer>> res;
        int n;
        int k;
        public List<List<Integer>> combine(int n, int k) {
            this.n = n;
            this.k = k;
            res = new ArrayList<>();
            temp = new ArrayList<>();
            dfs(1);//从1开始
            return res;
        }
        public void dfs(int begin){
            if (temp.size() == k){
                res.add(new ArrayList<>(temp));
            }else {
                //这里检索时是存在一个上界的，这是一个优化
                for (int i = begin; i <= n-(k-temp.size())+1 ; i++) {
                    temp.add(i);
                    dfs(i+1);//只能从比当前值大的时候作为起始点
                    temp.remove(temp.size()-1);
                }
            }
        }


        /**
         * 二刷：和一刷思路是一样的，只是k取值发生了一点变化
         * @param start 起始下标
         * @param n 最大值
         * @param k 剩余个数，这样剪枝更清晰了一些，初始时k直接传入题目中的k即可
         */
        public void dfs(int start, int n, int k, List<Integer> temp){
            if (k == 0) res.add(new ArrayList(temp));
            else{
                for (int i = start; i<=n-k+1; i++){//剪枝操作，根据当前k进行剪枝，时间快了14倍
                    temp.add(i);
                    dfs(i+1, n, k-1, temp);
                    temp.remove(temp.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}